package com.leetcode.algorithm.y22.m07;

import java.util.HashSet;
import java.util.Set;

/**
 * 1337. 矩阵中战斗力最弱的 K 行
 * 
 * https://leetcode.cn/problems/the-k-weakest-rows-in-a-matrix/
 * 
 * @author jie.deng
 *
 */
class Question1337Solution01 {

	public int[] kWeakestRows(int[][] mat, int k) {
		int[] kWeakestRows = new int[k];
		int kIdx = 0;
		Set<Integer> kWeakestRowsSet = new HashSet<>();
		for (int col = 0; col < mat[0].length && kIdx < k; col++) {
			for (int row = 0; row < mat.length && kIdx < k; row++) {
				if (kWeakestRowsSet.contains(row)) {
					continue;
				}
				if (mat[row][col] == 0) {
					kWeakestRows[kIdx++] = row;
					kWeakestRowsSet.add(row);
				}
			}
		}

		if (kIdx < k) {
			// case4补丁			
			for (int row = 0; row < mat.length && kIdx < k; row++) {
				if (kWeakestRowsSet.contains(row)) {
					continue;
				}
				kWeakestRows[kIdx++] = row;
			}
		}
		return kWeakestRows;
	}

}